AGC 013 题解
订不出 XJOI 的题就跑来 AGC 寻找安慰
$A$
管他升或者降，每次选尽量长的就完事了。贪心随便证一证。
$B$
脑筋急转弯题。路径倒过来看就是最后一个点没有出边。
考虑从中间切开。随便选一个点做切入点，从切入点不断深度遍历，直到当前点没有出边；这么做两次就找到俩端点了。
$C$
我又来力！
所有蚂蚁面目模糊的最终位置容易算。只要考虑 $1$ 号蚂蚁排名是啥就知道它最终位置是啥，其他蚂蚁的也就知道了。
想象 $0$ 处有一只哨兵蚂蚁，每有一只蚂蚁经过它，整体蚂蚁的排名就会左移/右移一位（自行脑补原因。。）
细节：$x_i \mod L < 0$ 时也会左移哦
$D$
$f_{i, j}$ 表示前 $i$ 个取完后黑色还有 $j$ 个，构成的不同颜色序列个数。然而你很快就发现，初始黑色不同、取球过程相同的时候这样会算重。
画出黑球个数的增减图像，显然我们统计的不是不同路径数，而是不同图像数。
我们定一种图像的特征点是其最低点碰到 $0$ 的版本。统计特征点个数即可，$dp_{i, j, 0/1}$ 表示前 $i$ 步做完，当前黑球个数为 $j$，是否碰到过 $0$。
- -B, +BW, -B : $-1$
- -B, +BW, -W : $0$
- -W, +BW, -B : $0$
- -W, +BW, -W : $+1$
1 & 2 均可能碰到 $0$。
$E$
$n$ 那么大，考虑矩乘。但是 $m$ 也很大啊，直接矩乘显然不现实。
考虑到柿子很简单，看看能不能用前缀和转移什么的。
$f_i = \sum\limits_{j = 0}^{i - 1} f_j (i - j)^2$
考虑从 $i$ 转移给 $i + 1$。将 $(i - j)$ 看作 $x_j$。
将转移给 $i + 1$ 的项整理成「在转移给 $i$ 的项的基础上修修补补」的形式：
$i$ 已标记
$f_{i + 1} = \sum\limits_{j = 0}^{i} f_j (x_j + 1)^2 = \sum\limits_{j = 0}^{i - 1} f_j x_j^2 + 2 f_j x_j + f_j$
$i$ 未标记
$f_{i + 1} = ( \sum\limits_{j = 0}^{i - 1} f_j (i + 1 - j)^2 ) + f_i = ( \sum\limits_{j = 0}^{i - 1} f_j x_j^2 + 2 f_j x_j + f_j ) + f_i$
令 $g_i = \sum\limits_{j = 0}^{i - 1} f_j x_j^2$
$h_i = \sum\limits_{j = 0}^{i - 1} 2 f_j x_j$
$s_i = \sum\limits_{j = 0}^{i - 1} f_j$
那么这三者转移有：
$g_{i + 1} = g_i + h_i + s_i$
$h_{i + 1} = h_i + 2 s_i$
$i$ 已标记：$s_{i + 1} = s_i$
$i$ 未标记：$s_{i + 1} = s_i + f_i = g_i + h_i + 2 s_i$
初始 $[g, h, s] = [0, 0, 1]$（艹，我真不是故意的我发誓）
答案：$mat[0][0]$
$F$
我会 $n^2 logn$!（迫真
这问题一看就要抽象化。
考虑如何判两个数组 $a$、$b$ 是否存在一种配对方式满足 $a_i \leq b_i$：对于 $a_i$, 执行一个从 $a_i$ 开始的后缀加；对于 $b_i$, 执行一个从 $b_i$ 开始的后缀减；存在配对方式当且仅当每个位置的值 $\geq 0$。
因为要最大化选正面的个数，先全部选正面。
如果不满足完全配对，我们可以这么做来修修补补：
- 对于 $first > second$ 的，可以给 $[second, first)$ 加一，花费 $1$ 的代价
- 对于询问插入的新牌，我们可以选择 $X$ 或者 $Y$，设选择的位置为 $p$，给 $[p, n) + 1$
可以看作，当前有一个有正有负的数组，我们有若干 $[second, first)$ 的区间，要求选最少的区间使得 $[1, p) \geq 0$, $[p, n] \geq -1$，其中 $p$ 未知。我们需要预处理每个 $p$ 的答案。
区间的选择分为两部分。
第一部分：先把 $< -1$ 的都搞掉，从右往左，每遇到一个 $< -1$ 的就使用包含它的区间中左端点最左的。如果区间用完了还没搞完，直接全部无解。
做完后还有区间没用完，不能浪费了——
第二部分：从前往后，碰到 $-1$ 就用询问加入的当前还没用的右端点最右的区间。这步是处理所有 $p$ 的答案。如果区间用完了，当前 $i$ 位置的 $-1$ 消不掉了，从 $i + 1$ 开始就不满足「$[1, p) \geq 0$」的要求了，所以 $p \in [i + 1, n]$ 全部无解。
$O(nlogn + Q)$。
总结：喜欢 $F$！